"""
https://leetcode.cn/problems/longest-palindromic-substring/description/
5. 最长回文子串
已解答
中等
相关标签
相关企业
提示
给你一个字符串 s，找到 s 中最长的
回文

子串
。



示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"


提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成
"""

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_len=1
        left_res=0
        right_res=0
        for i in range(len(s)):
            max_len_odd,left_odd,right_odd=self.max_pali_len_odd(s,i)
            max_len_even,left_even,right_even=self.max_pali_len_even(s,i)
            if max_len<max_len_odd:
                max_len=max_len_odd
                left_res=left_odd
                right_res=right_odd
            if max_len<max_len_even:
                max_len=max_len_even
                left_res=left_even
                right_res=right_even


        return s[left_res:right_res+1]

    def max_pali_len_odd(self,s:str,center:int)->(int,int,int):
        # 奇数情况
        left=center
        right=center
        max_len=1
        max_idx=len(s)-1
        while left>0 and right<max_idx:
            left-=1
            right+=1
            if s[left]==s[right]:
                max_len+=2
            else:
                left+=1
                right-=1
                break
        return (max_len,left,right)

    def max_pali_len_even(self,s:str,center_left:int)->(int,int,int):
        # 偶数情况
        left=center_left+1
        right=center_left
        max_len=0
        max_idx=len(s)-1
        while left>0 and right<max_idx:
            left-=1
            right+=1
            if s[left]==s[right]:
                max_len+=2
            else:
                left += 1
                right -= 1
                break
        return (max_len,left,right)




if __name__ == '__main__':
    s="cbbd"
    sol=Solution()
    max_str=sol.longestPalindrome(s)
    print(max_str)